package data_structure.tree;


import java.util.*;

/***
 *
 * 二叉树不同遍历方式
 *
 * */
public class TraverseTree {

    /**
     * 树的bfs(非递归)方式遍历
     */
    public List<TreeNode> bfs(TreeNode root) {

        List<TreeNode> result = new ArrayList<>();
        if (null == root) {
            return result;

        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {

            TreeNode treeNode = queue.poll();
            if (null == treeNode) {
                continue;
            }


            result.add(treeNode);
            if (null != treeNode.left) {
                queue.add(treeNode.left);
            }


            if (null != treeNode.right) {
                queue.add(treeNode.right);
            }

        }
        return result;
    }


    /**
     * dfs方式遍历树（非递归）
     */
    public List<TreeNode> dfs(TreeNode root) {

        List<TreeNode> result = new ArrayList<>();

        if (null == root) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();

        while (!stack.isEmpty()) {

            TreeNode treeNode = stack.pop();
            result.add(treeNode);
            if (treeNode.left != null) {
                stack.push(treeNode.left);
            }

            if (treeNode.right != null) {
                stack.push(treeNode.right);
            }

        }

        return result;
    }


    /**
     * bfs递归
     */
    public List<TreeNode> bfsRecursive(TreeNode root) {

        List<List<TreeNode>> tempList = new ArrayList<>();
        List<TreeNode> result = new ArrayList<>();

        if (root == null) return result;
        bfsSubMethod(root, 0, tempList);

        for (List<TreeNode> treeNodes : tempList) {
            result.addAll(treeNodes);
        }

        return result;
    }


    /***
     * bfs递归的子程序
     *
     * */
    private void bfsSubMethod(TreeNode root,
                              int level, List<List<TreeNode>> result) {
        if (root == null) return;
        if (result.size() <= level) {
            List<TreeNode> tmpList = new ArrayList<>();
            tmpList.add(root);
            result.add(tmpList);
        } else {
            List<TreeNode> tmpList = result.get(level);
            tmpList.add(root);
        }
        bfsSubMethod(root.left, level + 1, result);
        bfsSubMethod(root.right, level + 1, result);
    }


    /**
     * dfs 递归
     */
    public List<TreeNode> dfsRecursive(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        if (null == root) return result;
        dfsSubMethod(root, result);

        return result;
    }

    private void dfsSubMethod(TreeNode root, List<TreeNode> result) {
        if (null == root) {
            return;
        }
        result.add(root);
        dfsSubMethod(root.left, result);
        dfsSubMethod(root.right, result);
    }


}
